---
id: 5900f54a1000cf542c51005c
title: 'Завдання 477: гра «Послідовність чисел»'
challengeType: 1
forumTopicId: 302154
dashedName: problem-477-number-sequence-game
---

# --description--

Гра «Послідовність чисел» починається з послідовності $S$ з $N$ чисел, записаних в рядок.

Двоє гравців ходять по черзі. Гравець своєю чергою має обрати та видалити перше або останнє число, що залишилось в послідовності.

Рахунком гравця є сума всіх чисел, які він забрав. Кожен гравець намагається збільшити свою суму.

Якщо $N = 4$ та $S = \\{1, 2, 10, 3\\}$, то кожен гравець отримує максимально можливий рахунок ось так:

- Гравець 1: видаляє перше число (1)
- Гравець 2: видаляє останнє число з решти послідовності (3)
- Гравець 1: видаляє останнє число з решти послідовності (10)
- Гравець 2: видаляє число, яке залишилось (2)

Рахунок гравця 1 становить $1 + 10 = 11$.

Нехай $F(N)$ буде рахунком гравця 1, якщо обидва гравці дотримуються оптимальної стратегії для послідовності $S = \\{s_1, s_2, \ldots, s_N\\}$, визначеної як:

- $s_1 = 0$
- $s_{i + 1} = ({s_i}^2 + 45)$ modulo $1\\,000\\,000\\,007$

Послідовність починається з $S = \\{0, 45, 2\\,070, 4\\,284\\,945, 753\\,524\\,550, 478\\,107\\,844, 894\\,218\\,625, \ldots\\}$.

Дано, що $F(2) = 45$, $F(4) = 4\\,284\\,990$, $F(100) = 26\\,365\\,463\\,243$, $F(104) = 2\\,495\\,838\\,522\\,951$.

Знайдіть $F({10}^8)$.

# --hints--

`numberSequenceGame()` має повернути `25044905874565164`.

```js
assert.strictEqual(numberSequenceGame(), 25044905874565164);
```

# --seed--

## --seed-contents--

```js
function numberSequenceGame() {

  return true;
}

numberSequenceGame();
```

# --solutions--

```js
// solution required
```
